<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 7.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.5.1/css/all.min.css" integrity="sha256-wiz7ZSCn/btzhjKDQBms9Hx4sSeUYsDrTLg7roPstac=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancyapps-ui/5.0.28/fancybox/fancybox.css" integrity="sha256-6cQIC71/iBIYXFK+0RHAvwmjwWzkWd+r7v/BX3/vZDc=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/themes/green/pace-theme-minimal.css">
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/pace.min.js" integrity="sha256-gqd7YTjg/BtfqWSwsJOvndl0Bxc8gFImLEkXQT8+qj0=" crossorigin="anonymous"></script>

<script class="next-config" data-name="main" type="application/json">{"hostname":"sumumm.github.io","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.19.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":true,"style":"mac"},"fold":{"enable":true,"height":300},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":true,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":true,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="本文主要是数据结构——常见的查找方法相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。">
<meta property="og:type" content="article">
<meta property="og:title" content="LV03-13-数据结构-查找方法">
<meta property="og:url" content="https://sumumm.github.io/post/de5b0cf1.html">
<meta property="og:site_name" content="苏木">
<meta property="og:description" content="本文主要是数据结构——常见的查找方法相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503144415215.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/1.gif">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503181717869.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503190730938.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503191008660.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503192432254.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504064720751.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504065758723.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504071459246.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504072213357.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504075444324.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504080829381.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504082409289.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504103516463.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504110838954.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504112037009.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504112848906.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504114749785.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504153925233.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504163214158.png">
<meta property="og:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/2.gif">
<meta property="article:published_time" content="2022-04-25T01:48:14.000Z">
<meta property="article:modified_time" content="2025-06-13T16:25:56.991Z">
<meta property="article:author" content="苏木">
<meta property="article:tag" content="LV03-数据结构">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503144415215.png">


<link rel="canonical" href="https://sumumm.github.io/post/de5b0cf1.html">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://sumumm.github.io/post/de5b0cf1.html","path":"post/de5b0cf1.html","title":"LV03-13-数据结构-查找方法"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>LV03-13-数据结构-查找方法 | 苏木</title>
  








    <script src="/js/browser_tools_disable.js"></script>

  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<!-- hexo injector head_end start --><link rel="stylesheet" href="https://unpkg.com/hexo-next-tags-plus@latest/lib/tag_plus.css" media="defer" onload="this.media='all'"><!-- hexo injector head_end end --></head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">苏木</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">我的学习之路</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>苏木的家</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类页<span class="badge">42</span></a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档页<span class="badge">673</span></a></li><li class="menu-item menu-item-flink"><a href="/flink/" rel="section"><i class="fa fa-link fa-fw"></i>友人帐</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于我</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#1-%E6%9F%A5%E6%89%BE"><span class="nav-text">1.查找</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#2-%E9%A1%BA%E5%BA%8F%E6%9F%A5%E6%89%BE"><span class="nav-text">2.顺序查找</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#2-1%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95"><span class="nav-text">2.1查找方法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-ASL"><span class="nav-text">2. ASL </span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#3-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE"><span class="nav-text">3.二分查找</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#3-1%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95"><span class="nav-text">3.1查找方法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-2-ASL"><span class="nav-text">3.2 ASL </span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#4-%E5%88%86%E5%9D%97%E6%9F%A5%E6%89%BE"><span class="nav-text">4.分块查找</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#4-1%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95"><span class="nav-text">4.1查找方法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#4-2-ASL"><span class="nav-text">4.2 ASL </span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#5-Hash-%E8%A1%A8"><span class="nav-text">5. Hash 表</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#5-1-Hash-%E5%87%BD%E6%95%B0%E6%9E%84%E5%BB%BA"><span class="nav-text">5.1 Hash 函数构建</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#5-1-1%E7%9B%B4%E6%8E%A5%E5%AE%9A%E5%9D%80%E6%B3%95"><span class="nav-text">5.1.1直接定址法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-1-2%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95"><span class="nav-text">5.1.2数字分析法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-1-3%E5%B9%B3%E6%96%B9%E5%8F%96%E4%B8%AD%E6%B3%95"><span class="nav-text">5.1.3平方取中法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-1-4%E6%8A%98%E5%8F%A0%E6%B3%95"><span class="nav-text">5.1.4折叠法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-1-5%E9%9A%8F%E6%9C%BA%E6%95%B0%E6%B3%95"><span class="nav-text">5.1.5随机数法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-1-6%E9%99%A4%E7%95%99%E4%BD%99%E6%95%B0%E6%B3%95"><span class="nav-text">5.1.6除留余数法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5-2%E5%86%B2%E7%AA%81%E5%A4%84%E7%90%86"><span class="nav-text">5.2冲突处理</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#5-2-1%E5%BC%80%E6%94%BE%E5%9C%B0%E5%9D%80%E6%B3%95"><span class="nav-text">5.2.1开放地址法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-2-2%E9%93%BE%E5%9C%B0%E5%9D%80%E6%B3%95"><span class="nav-text">5.2.2链地址法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5-3%E7%BB%93%E6%9E%84%E4%BD%93%E5%AE%9E%E7%8E%B0"><span class="nav-text">5.3结构体实现</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5-4-Hash-%E8%A1%A8%E5%9F%BA%E6%9C%AC%E6%93%8D%E4%BD%9C"><span class="nav-text">5.4 Hash 表基本操作</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#5-4-1%E5%88%9B%E5%BB%BA"><span class="nav-text">5.4.1创建</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-4-2%E6%8F%92%E5%85%A5"><span class="nav-text">5.4.2插入</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-4-3%E6%9F%A5%E6%89%BE"><span class="nav-text">5.4.3查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#5-4-4%E6%98%BE%E7%A4%BA"><span class="nav-text">5.4.4显示</span></a></li></ol></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="苏木"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">苏木</p>
  <div class="site-description" itemprop="description">莫道桑榆晚，为霞尚满天</div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">673</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">42</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
        <span class="site-state-item-count">43</span>
        <span class="site-state-item-name">标签</span>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/sumumm" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;sumumm" rel="noopener me" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
  </div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://sumumm.github.io/post/de5b0cf1.html">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="苏木">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="苏木">
      <meta itemprop="description" content="莫道桑榆晚，为霞尚满天">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="LV03-13-数据结构-查找方法 | 苏木">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          LV03-13-数据结构-查找方法
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-04-25 09:48:14" itemprop="dateCreated datePublished" datetime="2022-04-25T09:48:14+08:00">2022-04-25</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/" itemprop="url" rel="index"><span itemprop="name">嵌入式开发</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/" itemprop="url" rel="index"><span itemprop="name">01HQ课程体系</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">LV03-数据结构</span></a>
        </span>
    </span>

  
    <span class="post-meta-break"></span>
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>7.2k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>26 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody"><p>本文主要是数据结构——常见的查找方法相关笔记，若笔记中有错误或者不合适的地方，欢迎批评指正😃。</p>
<span id="more"></span>

<!-- Photo: https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/ -->

<details class="folding-tag" blue><summary> 点击查看使用工具及版本 </summary>
              <div class='content'>
              <table>    <tr>        <td align="center" width=150px>Windows</td>        <td align="left">windows11</td>    </tr>    <tr>        <td align="center">Ubuntu</td>        <td align="left">Ubuntu16.04的64位版本</td>      </tr>    <tr>        <td align="center">VMware® Workstation 16 Pro</td>        <td align="left">16.2.3 build-19376536</td>      </tr>    <tr>        <td align="center">SecureCRT</td>        <td align="left">Version 8.7.2 (x64 build 2214)   -   正式版-2020年5月14日</td>      </tr>    <tr>        <td align="center">开发板</td>        <td align="left">正点原子 i.MX6ULL Linux阿尔法开发板</td>      </tr>    <tr>        <td align="center">uboot</td>        <td align="left">NXP官方提供的uboot，NXP提供的版本为uboot-imx-rel_imx_4.1.15_2.1.0_ga(使用的uboot版本为U-Boot 2016.03)</td>      </tr>    <tr>        <td align="center">linux内核</td>        <td align="left">linux-4.15(NXP官方提供)</td>      </tr>    <tr>        <td align="center">STM32开发板</td>        <td align="left">正点原子战舰V3(STM32F103ZET6)</td>      </tr></table>
              </div>
            </details>

<details class="folding-tag" blue><summary> 点击查看本文参考资料 </summary>
              <div class='content'>
              <table>    <tr><td align="center">参考方向  </td><td align="center">参考原文</td></tr>    <tr><td align="left">---</td><td align="left"><a href="" target="_blank">--- <i class="fa fa-external-link-alt"></i> </a></td></tr></table>
              </div>
            </details>

<details class="folding-tag" blue><summary> 点击查看相关文件下载 </summary>
              <div class='content'>
              <table>    <tr>        <td align="center">---</td>        <td align="left">--- <a href="" target="_blank">  <i class="fa fa-external-link-alt"></i></a></td>      </tr></table>
              </div>
            </details>

<h1 id="1-查找"><a href="#1-查找" class="headerlink" title="1.查找"></a><font size=3>1.查找</font></h1><p>设记录表$L&#x3D;(R_1,R_2,……,R_n)$，其中$R_i(l ≤ i ≤n)$为记录，对给定的某个值 k ，在表 L 中确定 key &#x3D; k 的记录的过程，称为查找。若表 L 中存在一个记录$R_i$的 key &#x3D; k ，记为$R_i.key &#x3D; k$，则查找成功，返回该记录在表L中的序号  i  (或$R_i $的地址)，否则(查找失败)返回 0 (或空地址 NULL )。表 L 就称为<strong>查找表</strong>，它是是由同一类型的数据元素构成的<strong>集合</strong>。</p>
<p>在查找表中只做查找操作，而不改动表中数据元素，称此类查找表为<strong>静态查找表</strong>，静态查找表既可以使用顺序表表示，也可以使用链表结构表示。反之，在查找表中做查找操作的同时进行插入数据或者删除数据的操作，称此类表为<strong>动态查找表</strong>。</p>
<p>查找的方法有这几种：顺序查找，二分查找（折半查找），分块查找和 hash 表查找等。</p>
<ul>
<li>平均查找长度</li>
</ul>
<p>对查找算法，主要分析其 T(n) （时间复杂度）。查找过程是 key 的比较过程，时间主要耗费在各记录的 key 与给定 k 值的比较上。比较次数越多，算法效率越差（即 T(n) 量级越高），故用比较次数刻画算法的 T(n) 。</p>
<p>平均查找长度 ASL （ Average Search Length ）：对给定 k ，有 n 个元素的查找表 L 中记录比较次数的期望值(或平均值)，即<br>$$<br>ASL&#x3D;\sum_{i &#x3D; 1}^{n}P_iC_i<br>$$<br>$P_i$为查找$R_i$的概率。等概率情况下$P_i&#x3D;1&#x2F;n$；$C_i$为查找$R_i$时$key$进行的比较次数(或查找次数)。 </p>
<h1 id="2-顺序查找"><a href="#2-顺序查找" class="headerlink" title="2.顺序查找"></a><font size=3>2.顺序查找</font></h1><h2 id="2-1查找方法"><a href="#2-1查找方法" class="headerlink" title="2.1查找方法"></a><font size=3>2.1查找方法</font></h2><p>静态查找表用顺序存储结构表示时，顺序查找的查找过程为：设给定值为 k ，在表$L&#x3D;(R_1,R_2,……,R_n)$中，从$R_n$开始，查找$key &#x3D; k$的记录。</p>
<p>实现代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">sqsearch</span><span class="params">(seqlist r, keytype k)</span>  </span><br><span class="line">&#123;   </span><br><span class="line">    <span class="type">int</span> i;</span><br><span class="line">	r.data[<span class="number">0</span>].key = k;  <span class="comment">/* k存入监视哨 */</span></span><br><span class="line">	i = r.len;          <span class="comment">/* 取表长 */</span></span><br><span class="line">	<span class="keyword">while</span>(r.data[i].key != k) </span><br><span class="line">        i--;  </span><br><span class="line">	<span class="keyword">return</span> (i);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<details class="folding-tag" blue><summary> 点击查看什么是监视哨 </summary>
              <div class='content'>
              <p>在程序中初始化创建查找表时，由于是顺序存储，所以会将所有的数据元素存储在数组中，但是把<strong>第一个位置</strong>留给了用户用于查找的关键字，顺序表的一端添加用户用于搜索的关键字，称作<strong>监视哨</strong>。</p><img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503144415215.png" alt="image-20220503144415215" style="zoom:33%;" />
              </div>
            </details>

<h2 id="2-ASL"><a href="#2-ASL" class="headerlink" title="2. ASL "></a><font size=3>2. ASL </font></h2><p>表中有  n  个数据元素，查找第一个元素时需要比较  n  次；查找最后一个元素时需要比较  1  次，所以有 $C_i &#x3D; n – i + 1$，假设这 n 个数的被查找到的概率是相同的，则有：<br>$$<br>ASL &#x3D; \sum_{i &#x3D; 1}^n\frac{1}{n}(n - i + 1) &#x3D; \frac{n+1}{2}<br>$$<br>这个平均查找长度是在假设查找算法每次都成功的前提下得出的。而对于查找算法来说，查找成功和查找失败的概率是相同的，查找算法的平均查找长度应该为<strong>查找成功时的平均查找长度加上查找失败时的平均查找长度</strong>。若每次都查找失败，那么比较的次数都是 n + 1 ，所以最终 ASL 为：<br>$$<br>ASL &#x3D; \frac{1}{2}\sum_{i &#x3D; 1}^n\frac{1}{n}(n - i + 1) + \frac{1}{2}(n + 1) &#x3D; \frac{3}{4}(n + 1)<br>$$<br>【缺点】这样算下来，查找的效率是很低的，查找某记录几乎要扫描整个表，当表长 n 很大时，会令人无法忍受。</p>
<h1 id="3-二分查找"><a href="#3-二分查找" class="headerlink" title="3.二分查找"></a><font size=3>3.二分查找</font></h1><h2 id="3-1查找方法"><a href="#3-1查找方法" class="headerlink" title="3.1查找方法"></a><font size=3>3.1查找方法</font></h2><p>二分查找也叫作折半查找，在某些情况下相比于顺序查找，效率会更高。但是该算法的使用的前提是静态查找表中的<strong>数据必须是有序的</strong>。</p>
<p>算法思路：对给定值 k ，逐步确定待查记录所在区间，每次将搜索空间减少一半(折半)，直到查找成功或失败为止。</p>
<p>设两个游标 low 、 high ，分别指向当前待查找表的上界(表头)和下界(表尾)， mid 指向中间元素。</p>
<details class="folding-tag" blue><summary> 点击查看中间元素计算 </summary>
              <div class='content'>
              <p>$$<br>mid &#x3D; [\frac{low + high}{2}]<br>$$<br>很多时候， mid 计算出来并不为整数，所以还需要进行<strong>取整</strong>操作。</p>
              </div>
            </details>

<p>如下图所示：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/1.gif" alt="1" style="zoom:50%;" />

<p>实现代码如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">Binsearch</span><span class="params">(seqlist r, keytype k)</span>    <span class="comment">/* 对有序表 r 折半查找的算法 */</span></span><br><span class="line">&#123;  </span><br><span class="line">    <span class="type">int</span> low, high, mid;  </span><br><span class="line">    low = <span class="number">1</span>;</span><br><span class="line">	high = r.len; </span><br><span class="line">    <span class="keyword">while</span> (low &lt;= high)    </span><br><span class="line">    &#123;  </span><br><span class="line">        mid = (low+high) / <span class="number">2</span>;   </span><br><span class="line">        <span class="keyword">if</span> (k == r.data[mid].key)  </span><br><span class="line">            <span class="keyword">return</span> (mid);  </span><br><span class="line">        <span class="keyword">if</span> (k &lt; r.data[mid].key) </span><br><span class="line">            high = mid - <span class="number">1</span>;  </span><br><span class="line">        <span class="keyword">else</span> </span><br><span class="line">            low = mid + <span class="number">1</span>;</span><br><span class="line">    &#125;      </span><br><span class="line">     <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> &#125;     </span><br></pre></td></tr></table></figure>

<h2 id="3-2-ASL"><a href="#3-2-ASL" class="headerlink" title="3.2 ASL "></a><font size=3>3.2 ASL </font></h2><p>折半查找的运行过程可以用二叉树来描述，这棵树通常称为判定树。把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树，由此得到的二叉树，称为描述二分查找的判定树( Decision Tree )或比较树。</p>
<details class="folding-tag" blue><summary> 二叉判定树怎么画？ </summary>
              <div class='content'>
              <ul><li>长度为 n 的查找表二叉判定树构造方法：</li></ul><p>（1）当 n &#x3D; 0 时，二分查找判定树为空；</p><p>（2）当 n ＞ 0 时，二分查找判定树的根结点是查找表中序号为 mid &#x3D; (1 + n) &#x2F; 2 的记录，根结点的左子树是与有序表 L[1] ~ L[mid - 1] 相对应的折半查找判定树，根结点的右子树是与 L[mid + 1] ~ L[n] 相对应的二分查找判定树。</p>
              </div>
            </details>

<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503181717869.png" alt="image-20220503181717869" style="zoom:33%;" />

<p>假设表长$n &#x3D; 2^h -1$，$h &#x3D; \log_2(n+1)$，记录数 n 恰好为一棵 h 层的满二叉树的结点数，则得出的判定树如上图。此时有：<br>$$<br>ASL &#x3D; \sum_{i&#x3D;1}^nP_iC_i&#x3D;\frac{1}{n}\sum_{i&#x3D;1}^hi·2^{i-1}<br>$$</p>
<p>$$<br>\text{令} S &#x3D; \sum_{i&#x3D;1}^hi·2^{i-1}&#x3D;1·2^0+2·2^1+3·2^2+…+(h-2)·2^{h-2}+(h-1)·2^{h-1}<br>$$</p>
<p>$$<br>\text{则} 2S &#x3D; 2·\sum_{i&#x3D;1}^hi·2^{i-1}&#x3D;1·2^1+2·2^2+3·2^3+…+(h-2)·2^{h-1}+(h-1)·2^{h}<br>$$</p>
<p>$$<br>\text{则} S &#x3D; 2S - S &#x3D; h·2^{h}-(2^0+2^1+2^2+…+2^{h-2}+2^{h-1})&#x3D;h·2^h-(2^h-1)&#x3D;(n+1)\log_2(n+1)-n<br>$$</p>
<p>$$<br>\text{所以} ASL&#x3D;\frac{n+1}{n}\log_2(n+1)-1<br>$$</p>
<p>二分查找法的平均查找长度显然要比顺序查找方法更优。</p>
<h1 id="4-分块查找"><a href="#4-分块查找" class="headerlink" title="4.分块查找"></a><font size=3>4.分块查找</font></h1><h2 id="4-1查找方法"><a href="#4-1查找方法" class="headerlink" title="4.1查找方法"></a><font size=3>4.1查找方法</font></h2><p>分块查找，也叫索引顺序查找，算法实现除了需要查找表本身之外，还需要根据查找表建立一个索引表。</p>
<ul>
<li>分块</li>
</ul>
<p>设记录表长为 n ，将表的 n 个记录分成$b&#x3D;[n&#x2F;s]$个块，每块 s 个记录（最后一块记录数可以少于 s 个），即：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503190730938.png" alt="image-20220503190730938" style="zoom: 50%;" />

<p>且<strong>表分块有序</strong>，即第 i（1 ≤ i ≤ b-1） 块所有记录的 key 小于第 i + 1 块中记录的  key ，但<strong>块内记录可以无序</strong>。</p>
<ul>
<li>建立索引</li>
</ul>
<p>每块对应一个索引项，其中$k_{max}$为该块内记录的最大 key ， link 为该块第一记录的序号（或指针）。</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503191008660.png" alt="image-20220503191008660" style="zoom: 50%;" />

<details class="folding-tag" blue><summary> 点击查看实例 </summary>
              <div class='content'>
              <p>设表长为 n &#x3D; 8 ，取 s &#x3D; 3 ，$b &#x3D; [8&#x2F;3]&#x3D;3$，即分为 3 块，每块 3 个元素，最后一块不足 3 个元素，只有两个元素。如下图所示：</p><img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220503192432254.png" alt="image-20220503192432254" style="zoom: 33%;" /><p>若查找 k &#x3D; 19 的记录，索引表是按照$k_{max}$有序的，可对其折半查找，而块内按顺序方法查找。</p>
              </div>
            </details>

<h2 id="4-2-ASL"><a href="#4-2-ASL" class="headerlink" title="4.2 ASL "></a><font size=3>4.2 ASL </font></h2><p>分块查找算法的运行效率受两部分影响：查找块的操作和块内查找的操作。查找块的操作可以采用顺序查找，也可以采用折半查找（会更好一些）。块内查找的操作采用顺序查找的方式。</p>
<p>相比于折半查找，分块查找时间效率上更低一些。相比于顺序查找，由于在子表中进行，比较的子表个数会不同程度的减少，所有分块查找算法会更优。</p>
<p>总的来说。分块查找的 ASL 介于顺序查找和二分查找之间。</p>
<h1 id="5-Hash-表"><a href="#5-Hash-表" class="headerlink" title="5. Hash 表"></a><font size=3>5. Hash 表</font></h1><p>上边介绍了三种查找方法，但是都是需要经过大量的比较。其实理想的查找方法是：对给定的 k ，不经任何比较便能获取所需的记录，其查找的时间复杂度为常数级 O(C) 。这就要求在建立记录表的时候，确定记录的 key 与其存储地址之间的关系 f ，即使 key 与记录的存放地址 H 相对应：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504064720751.png" alt="image-20220504064720751" style="zoom: 33%;" />







<p>当我们需要查找 key &#x3D; k 的记录时，通过关系 f 就可得到相应记录的地址而获取记录，从而免去了 key 的比较过程，这个关系 f 就是所谓的 Hash 函数（或称散列函数、杂凑函数），记为 H(key) 。 H(key) 实际上是一个地址映象函数，其自变量为记录的 key ，函数值为记录的存储地址（或称 Hash 地址）。</p>
<p>不同的 key 可能得到同一个 Hash 地址，即当 keyl !&#x3D; key2 时，可能有 H(key1) &#x3D; H(key2) ，此时称  key1 和 key2 为<strong>同义词</strong>。这种现象称为<strong>冲突</strong>或碰撞，因为<strong>一个数据单位只可存放一条记录</strong>。选取 Hash 函数只能做到使冲突尽可能少，却不能完全避免。</p>
<p>根据选取的 Hash 函数 H(key) 和处理冲突的方法，将一组记录$(R_1 R_2……R_n)$映象到记录的存储空间，所得到的记录表称为 Hash 表。</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504065758723.png" alt="image-20220504065758723" style="zoom: 33%;" />



<h2 id="5-1-Hash-函数构建"><a href="#5-1-Hash-函数构建" class="headerlink" title="5.1 Hash 函数构建"></a><font size=3>5.1 Hash 函数构建</font></h2><p>在设计哈希函数时，要尽量地避免冲突现象的发生。常用的 Hash 函数构造方法有这几种：直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法。</p>
<h3 id="5-1-1直接定址法"><a href="#5-1-1直接定址法" class="headerlink" title="5.1.1直接定址法"></a><font size=3>5.1.1直接定址法</font></h3><p>直接定址法的 Hash 函数是一次函数：<br>$$<br>H(key) &#x3D; a * key + b<br>$$<br>其中  H（key） 表示关键字为  key  对应的哈希地址， a  和  b  都为常数。</p>
<p>例如，很多时候我们接受了服务后，都可能会对客服做评价，评价分数为 60 、 70 、 80 、 90 、 100 这几个层次，通过直接定址法建立 Hash 表：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504071459246.png" alt="image-20220504071459246" style="zoom: 50%;" />

<p>现在我们要查找 90 分的人数，那么我们带入 90 到 Hash 中，会直接得到其 Hash 地址 04 （求得的哈希地址表示该记录的位置在查找表的第  04  位）。</p>
<h3 id="5-1-2数字分析法"><a href="#5-1-2数字分析法" class="headerlink" title="5.1.2数字分析法"></a><font size=3>5.1.2数字分析法</font></h3><p>如果关键字由多位字符或者数字组成，就可以考虑抽取其中的  2  位或者多位作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免冲突发生。</p>
<p>例如，下图为一组数据的部分关键字，他们都是由 10 位十进制数（全为 0-9 ）组成的:</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504072213357.png" alt="image-20220504072213357" style="zoom: 50%;" />

<p>通过分析关键字的构成，很明显可以看到只有中间绿色部分取值近似随机，所以为了避免冲突，可以这一部分中任意选取 几 位作为其哈希地址。</p>
<h3 id="5-1-3平方取中法"><a href="#5-1-3平方取中法" class="headerlink" title="5.1.3平方取中法"></a><font size=3>5.1.3平方取中法</font></h3><p>平方取中法就是对关键字做平方操作，取中间得几位作为哈希地址。例如，</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504075444324.png" alt="image-20220504075444324" style="zoom:50%;" />

<p>可以看到平方后开头两位各不相同，于是可以取开头两位作为其 Hash 地址。</p>
<h3 id="5-1-4折叠法"><a href="#5-1-4折叠法" class="headerlink" title="5.1.4折叠法"></a><font size=3>5.1.4折叠法</font></h3><p>折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。折叠的方式有两种，一种是移位折叠，一种是间界折叠。</p>
<p>例如，图书馆某本书的编号为 0-520-1314-5 ，则有：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504080829381.png" alt="image-20220504080829381" style="zoom: 33%;" />

<p>移位折叠就是将分割后的每一小部分，按照其最低位进行对齐，然后相加；间界折叠是从一端向另一端沿分割线来回折叠。</p>
<h3 id="5-1-5随机数法"><a href="#5-1-5随机数法" class="headerlink" title="5.1.5随机数法"></a><font size=3>5.1.5随机数法</font></h3><p>随机数法就是取关键字的一个随机函数值作为它的 Hash 地址，即： H(key)&#x3D;random（key） ，此方法<strong>适用于关键字长度不等</strong>的情况。这里的随机函数其实是伪随机函数，随机函数是即使每次给定的  key  相同，但是  H(key) 都是不同，而伪随机函数正好相反，每个  key  都对应的是固定的  H(key) 。</p>
<h3 id="5-1-6除留余数法"><a href="#5-1-6除留余数法" class="headerlink" title="5.1.6除留余数法"></a><font size=3>5.1.6除留余数法</font></h3><p>若已知整个 Hash 表的最大长度  m ，可以取一个不大于  m  的数  p ，然后对该关键字  key  做取余运算，即： H(key) &#x3D; key % p 。例如，</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504082409289.png" alt="image-20220504082409289" style="zoom:50%;" />

<p>由上图可知， p &#x3D; 21 时，包含质数因子 7 的 key 都可能被映象到相同的单元，冲突现象严重。当 p &#x3D; 19 时， H(key) 的随机度就好多了。</p>
<p>【注意】对于  p  的取值非常重要，一般来说 p 可以为不大于  m  的质数或者不包含小于  20  的质因数的合数。</p>
<h2 id="5-2冲突处理"><a href="#5-2冲突处理" class="headerlink" title="5.2冲突处理"></a><font size=3>5.2冲突处理</font></h2><p>选取随机度好的 Hash 函数可使冲突减少，一般来讲不能完全避免冲突。设 Hash 表地址空间为 0～m-1 （表长为 m ）:</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504103516463.png" alt="image-20220504103516463" style="zoom:50%;" />

<p>表中某地址$j \in [0，m-1]$中己存放有记录，而另一个记录的 H(key) 值也为 j 此时就会产生冲突。</p>
<p>处理冲突的方法一般为：在地址 j 的前面或后面找一个空闲单元存放冲突的记录，或将相冲突的诸记录拉成链表。在处理冲突的过程中，可能发生一连串的冲突现象，即可能得到一个地址序列$H_1,H_2,…,H_n,H_i\in[0，m-1]$。$H_1$是冲突时选取的下一地址，而$H_1$中可能己有记录，又需要设法得到下一地址$H_2$，直到某个$H_n$不发生冲突为止。这种现象称为<strong>聚积</strong>，它严重影响了 Hash 表的查找效率，聚积的发生也会加重冲突。</p>
<p>还有一个重要的因素是表的<strong>装填因子</strong> α ， α &#x3D; n &#x2F; m  ，其中 m 为表长， n 为表中记录个数。一般 α 在 0.7～0.8 之间，使表保持一定的空闲余量，以减少冲突和聚积现象。</p>
<h3 id="5-2-1开放地址法"><a href="#5-2-1开放地址法" class="headerlink" title="5.2.1开放地址法"></a><font size=3>5.2.1开放地址法</font></h3><p>当发生冲突时，在 H(key) 的前后找一个空闲单元来存放冲突的记录，即在 H(key) 的基础上获取下一地址：<br>$$<br>H_i &#x3D; (H(key) + d_i)%m<br>$$<br>其中 m 为表长， % 运算是保证$H_i$落在 [0，m-1] 区间；$d_i$为地址增量，它的取法有多中种：</p>
<p>（1）线性探测法：$d_i &#x3D; 1,2,3,…,(m-1)$，即当遇到冲突时，从发生冲突位置起，每次  +1 ，向右探测，直到有空闲的位置为止。</p>
<p>（2）二次探测法：$d_i &#x3D; 1^2,-1^2,2^2,-2^2,…$，即从发生冲突的位置起，按照 如$+1^2,-1^2,+2^2,-2^2,…$此探测，直到有空闲的位置。</p>
<p>（3）伪随机数探测法：$d &#x3D; \text{伪随机数}$，即每次加上一个随机数，直到探测到空闲位置结束。</p>
<ul>
<li>实例</li>
</ul>
<p>设记录的 key 集合 k &#x3D; {23, 34, 14, 38, 46, 16, 68, 15, 7, 31, 26}  ，记录数 n &#x3D; 11 ，令装填因子 α &#x3D; 0.75 ，则表长 m &#x3D; [n &#x2F; α] &#x3D; 15 ，使用除留余数法选取 Hash 函数，取 p &#x3D; 13 ，则 H(key) &#x3D; key % 13 ，建立 Hash 表，则有：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504110838954.png" alt="image-20220504110838954" style="zoom:50%;" />

<p>会发现有两个地方产生了冲突，下边使用开放地址法进行处理，重新放置的地址为：<br>$$<br>H_i &#x3D; (H(key)+d_i)%15<br>$$<br>所以有：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504112037009.png" alt="image-20220504112037009" style="zoom: 50%;" />

<h3 id="5-2-2链地址法"><a href="#5-2-2链地址法" class="headerlink" title="5.2.2链地址法"></a><font size=3>5.2.2链地址法</font></h3><p>我们还可以在发生冲突时，将各冲突记录链在一起，即同义词的记录存于同一<strong>链表</strong>。即可以设 H(key) 取值范围（值域）为 [0，m-1] ，建立头指针向量 HP[i] (0 ≤ i ≤ m-1) ，其中 HP[i] 初始值为空。</p>
<p>HP[i]（0≤i≤m-l）初值为空。 </p>
<ul>
<li>实例</li>
</ul>
<p>设记录的 key 集合 k &#x3D; {23, 34, 14, 38, 46, 16, 68, 15, 7, 31, 26}  ，则通过 Hash 函数 H(key) &#x3D; key % 13 得到：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504112848906.png" alt="image-20220504112848906" style="zoom:50%;" />

<p>通过链地址法建立 Hash 表，则有：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504114749785.png" alt="image-20220504114749785" style="zoom:50%;" />

<p>链地址法解决冲突的优点：无聚积现象；删除表中记录容易实现。</p>
<h2 id="5-3结构体实现"><a href="#5-3结构体实现" class="headerlink" title="5.3结构体实现"></a><font size=3>5.3结构体实现</font></h2><p>首先我们需要一个数组存储 Hash 表地址，这个其实是用于存储 key 对 p 取的余数，接着后边使用链地址法处理所有冲突，链表节点我们使用三个域表示，数据域 key 存储原始数据，数据域 value 存储余数，也就是数据在 Hash 表中的地址，最后是一个指针域，指向下一个节点。节点结构如下图：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504153925233.png" alt="image-20220504153925233" style="zoom:33%;" />

<p>结构体定义如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/* 宏定义 */</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> N 12 <span class="comment">/* Hash表长度 */</span></span></span><br><span class="line"></span><br><span class="line"><span class="comment">/* 自定义数据类型 */</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> data_h;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">hash_node</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	data_h key;  <span class="comment">/* 存放原始的数据 */</span></span><br><span class="line">	data_h value;<span class="comment">/* 存放余数 */</span></span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">hash_node</span> * <span class="title">next</span>;</span></span><br><span class="line">&#125;hslinkednode, * hslinkedlink;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> </span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	hslinkednode data[N]; <span class="comment">/* 地址表 */</span></span><br><span class="line">&#125;hash;</span><br></pre></td></tr></table></figure>

<h2 id="5-4-Hash-表基本操作"><a href="#5-4-Hash-表基本操作" class="headerlink" title="5.4 Hash 表基本操作"></a><font size=3>5.4 Hash 表基本操作</font></h2><p>完整源代码可点击这里下载：</p>
<table>
    <tr>
        <td align="center" width=150>数据结构</td>
        <td align="left"><a href="https://wwz.lanzouy.com/b036z50af" target="_blank">查找  <i class="fa fa-external-link-alt"></i> </a>  (密码:b1y3)</td>  
    </tr>
</table>


<h3 id="5-4-1创建"><a href="#5-4-1创建" class="headerlink" title="5.4.1创建"></a><font size=3>5.4.1创建</font></h3><p>创建一个 Hash 表数组，数组中每个元素都是 Hash 表节点类型，如下图：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/image-20220504163214158.png" alt="image-20220504163214158" style="zoom:33%;" />

<p>【注意】数组中的元素，后边都相当于链表头节点。</p>
<details class="folding-tag" blue><summary> 点击查看函数实现 </summary>
              <div class='content'>
              <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * @Function: slinkedlist_create</span></span><br><span class="line"><span class="comment"> * @Description: Hash表创建</span></span><br><span class="line"><span class="comment"> * @param   : none</span></span><br><span class="line"><span class="comment"> * @return  : 返回一个地址</span></span><br><span class="line"><span class="comment"> *            NULL,内存申请失败;</span></span><br><span class="line"><span class="comment"> *            HP,Hash表地址</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">hash * <span class="title function_">hashlist_create</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="comment">/* 定义一个Hash表结构体指针变量 */</span></span><br><span class="line">	hash * HP;</span><br><span class="line">	<span class="comment">/* 1. 申请内存空间 */</span></span><br><span class="line">	HP = (hash *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(hash));</span><br><span class="line">	<span class="comment">/* 2. 判断是否申请成功 */</span></span><br><span class="line">	<span class="keyword">if</span> (HP == <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot; hash list malloc failed!\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> HP;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/* 3. 初始化内存空间 */</span></span><br><span class="line">	<span class="built_in">memset</span>(HP, <span class="number">0</span>, <span class="keyword">sizeof</span>(hash));</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> HP;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
              </div>
            </details>

<h3 id="5-4-2插入"><a href="#5-4-2插入" class="headerlink" title="5.4.2插入"></a><font size=3>5.4.2插入</font></h3><p>插入节点的过程如下图所示：</p>
<img data-src="https://fanhua-picture.oss-cn-hangzhou.aliyuncs.com/01%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%BC%80%E5%8F%91/01HQ%E8%AF%BE%E7%A8%8B%E4%BD%93%E7%B3%BB/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/LV03-13-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%9F%A5%E6%89%BE%E6%96%B9%E6%B3%95/img/2.gif" alt="2" style="zoom:50%;" />

<p>【注意】当产生冲突的时候，可以将数据通过链表相连接，在插入的时候注意<strong>有序插入</strong>。</p>
<details class="folding-tag" blue><summary> 点击查看函数实现 </summary>
              <div class='content'>
              <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * @Function: hashlist_insert</span></span><br><span class="line"><span class="comment"> * @Description: Hash表数据插入</span></span><br><span class="line"><span class="comment"> * @param HP: Hash表地址</span></span><br><span class="line"><span class="comment"> * @param key: 要插入的数据</span></span><br><span class="line"><span class="comment"> * @return  : 返回一个数值</span></span><br><span class="line"><span class="comment"> *            0,插入成功;</span></span><br><span class="line"><span class="comment"> *            -1,Hash表不存在或者节点内存申请失败</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="type">int</span> <span class="title function_">hashlist_insert</span><span class="params">(hash * HP, data_h key)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="comment">/* 定义两个Hash表节点结构体指针变量 */</span></span><br><span class="line">	hslinkedlink p;</span><br><span class="line">	hslinkedlink q;</span><br><span class="line">	<span class="comment">/* 1. 判断Hash表是否存在 */</span></span><br><span class="line">	<span class="keyword">if</span> (HP == <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot; hash list is not exited!\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/* 2. 新建节点并初始化 */</span></span><br><span class="line">	p = (hslinkedlink)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(hslinkednode));</span><br><span class="line">	<span class="keyword">if</span>(p == <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;The new hash list node malloc failed!\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	p-&gt;key = key;</span><br><span class="line">	p-&gt;value = key % N;</span><br><span class="line">	p-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">	<span class="comment">/* 3. 插入节点 */</span></span><br><span class="line">	q = &amp;(HP-&gt;data[p-&gt;value]);</span><br><span class="line">	<span class="comment">/* 有序插入，从小到大 */</span></span><br><span class="line">	<span class="keyword">while</span>((q-&gt;next !=<span class="literal">NULL</span>) &amp;&amp; (q-&gt;next-&gt;key &lt; p-&gt;key))</span><br><span class="line">	&#123;</span><br><span class="line">		q = q-&gt;next;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/* 4. 插入节点 */</span></span><br><span class="line">	p-&gt;next = q-&gt;next;</span><br><span class="line">	q-&gt;next = p;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
              </div>
            </details>

<h3 id="5-4-3查找"><a href="#5-4-3查找" class="headerlink" title="5.4.3查找"></a><font size=3>5.4.3查找</font></h3><details class="folding-tag" blue><summary> 点击查看函数实现 </summary>
              <div class='content'>
              <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * @Function: hashlist_search</span></span><br><span class="line"><span class="comment"> * @Description: Hash表数据查询</span></span><br><span class="line"><span class="comment"> * @param HP: Hash表地址</span></span><br><span class="line"><span class="comment"> * @param key: 要查询的数据</span></span><br><span class="line"><span class="comment"> * @return  : 返回一个地址</span></span><br><span class="line"><span class="comment"> *            other,数据节点地址;</span></span><br><span class="line"><span class="comment"> *            NULL,Hash表不存在或者节点内存申请失败</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line">hslinkedlink <span class="title function_">hashlist_search</span><span class="params">(hash * HP, data_h key)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="comment">/* 定义一个Hash表节点结构体指针变量 */</span></span><br><span class="line">	hslinkedlink p;</span><br><span class="line">	<span class="comment">/* 1. 判断Hash表是否存在 */</span></span><br><span class="line">	<span class="keyword">if</span> (HP == <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot; hash list is not exited!\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/* 2. 寻找Hash表key的存储位置的首节点 */</span></span><br><span class="line">	p = &amp;(HP-&gt;data[key % N]);</span><br><span class="line">	<span class="comment">/* 3. 查找数据 */</span></span><br><span class="line">	<span class="keyword">while</span> ((p-&gt;next !=<span class="literal">NULL</span>) &amp;&amp; (p-&gt;next-&gt;key != key)) </span><br><span class="line">	&#123;</span><br><span class="line">		p = p-&gt;next;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/* 4. 判断是否查询到 */</span></span><br><span class="line">	<span class="keyword">if</span> (p-&gt;next == <span class="literal">NULL</span>) </span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;The data is not in this hash list!\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line">	&#125; </span><br><span class="line">	<span class="keyword">else</span> </span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;The data is in this hash list!\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> p-&gt;next;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
              </div>
            </details>

<h3 id="5-4-4显示"><a href="#5-4-4显示" class="headerlink" title="5.4.4显示"></a><font size=3>5.4.4显示</font></h3><details class="folding-tag" blue><summary> 点击查看函数实现 </summary>
              <div class='content'>
              <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * @Function: hashlist_show</span></span><br><span class="line"><span class="comment"> * @Description: Hash表打印</span></span><br><span class="line"><span class="comment"> * @param HP: Hash表地址</span></span><br><span class="line"><span class="comment"> * @param key: 要查询的数据</span></span><br><span class="line"><span class="comment"> * @return  : 返回一个地址</span></span><br><span class="line"><span class="comment"> *            0,显示完成;</span></span><br><span class="line"><span class="comment"> *            -1,Hash表不存在</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="type">int</span> <span class="title function_">hashlist_show</span><span class="params">(hash * HP)</span></span><br><span class="line">&#123;</span><br><span class="line">	<span class="comment">/* 定义一个Hash表节点结构体指针变量 */</span></span><br><span class="line">	hslinkedlink p;</span><br><span class="line">	<span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line">	<span class="comment">/* 1. 判断Hash表是否存在 */</span></span><br><span class="line">	<span class="keyword">if</span> (HP == <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot; hash list is not exited!\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">/* 2. 访问Hash表 */</span></span><br><span class="line">	<span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; N; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		p = &amp;(HP-&gt;data[i]);</span><br><span class="line">		<span class="keyword">if</span>(p-&gt;next != <span class="literal">NULL</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;Hash data[%d]:&quot;</span>, i);</span><br><span class="line">			<span class="keyword">while</span>(p-&gt;next != <span class="literal">NULL</span>)</span><br><span class="line">			&#123;</span><br><span class="line">				<span class="built_in">printf</span>(<span class="string">&quot;%d-&gt;&quot;</span>,p-&gt;next-&gt;key);</span><br><span class="line">				p = p-&gt;next;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="built_in">puts</span>(<span class="string">&quot;NULL&quot;</span>);</span><br><span class="line">		&#125;	</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;Hash data[%d]:NULL\n&quot;</span>, i);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">puts</span>(<span class="string">&quot;&quot;</span>);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
              </div>
            </details>


    </div>

    
    
    

    <footer class="post-footer">




    <div>
        
            <div style="text-align:center;color: #ccc;font-size:14px;">
            ----------本文结束
            <i class="fas fa-fan fa-spin" style="color: #FF1493; font-size: 1rem"></i>
            感谢您的阅读----------
            </div>
        
    </div>





  
  <div class="my_post_copyright"> 
    <p><span>文章标题:</span><a href="/post/de5b0cf1.html">LV03-13-数据结构-查找方法</a></p>
    <p><span>文章作者:</span><a href="/" title="欢迎访问 《苏木》 的学习笔记">苏木</a></p>
    <p><span>发布时间:</span>2022年04月25日 - 09:48</p>
    <p><span>最后更新:</span>2025年06月14日 - 00:25</p>
    <p><span>原始链接:</span><a href="/post/de5b0cf1.html" title="LV03-13-数据结构-查找方法">https://sumumm.github.io/post/de5b0cf1.html</a></p>
    <p><span>许可协议:</span><i class="fab fa-creative-commons"></i> <a rel="license" href= "https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank" title="Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)">署名-非商业性使用-禁止演绎 4.0 国际</a> 转载请保留原文链接及作者。</p>  
  </div>
  


          <div class="post-tags">
              <a href="/tags/LV03-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"><i class="fa fa-tag"></i> LV03-数据结构</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/post/34db0ced.html" rel="prev" title="LV04-01-文件操作-文件的相关概念">
                  <i class="fa fa-angle-left"></i> LV04-01-文件操作-文件的相关概念
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/post/5f170582.html" rel="next" title="LV03-12-数据结构-二叉树的遍历">
                  LV03-12-数据结构-二叉树的遍历 <i class="fa fa-angle-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">

  <div class="copyright">
    &copy; 2017 – 
    <span itemprop="copyrightYear">2025</span>
    <span class="with-love">
      <i class="fa fa-heart"></i>
    </span>
    <span class="author" itemprop="copyrightHolder">苏木</span>
  </div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
      <span>站点总字数：</span>
    <span title="站点总字数">3.7m</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
      <span>站点阅读时长 &asymp;</span>
    <span title="站点阅读时长">225:26</span>
  </span>
</div>




    <span id="sitetime"></span>
    <script defer language=javascript>
        function siteTime()
        {
            window.setTimeout("siteTime()", 1000);
            var seconds = 1000;
            var minutes = seconds * 60;
            var hours = minutes * 60;
            var days = hours * 24;
            var years = days * 365;
            var today = new Date();
            var todayYear = today.getFullYear();
            var todayMonth = today.getMonth()+1;
            var todayDate = today.getDate();
            var todayHour = today.getHours();
            var todayMinute = today.getMinutes();
            var todaySecond = today.getSeconds();
            /*==================================================
            Date.UTC() -- 返回date对象距世界标准时间(UTC)1970年1月1日午夜之间的毫秒数(时间戳)
            year        - 作为date对象的年份，为4位年份值
            month       - 0-11之间的整数，做为date对象的月份
            day         - 1-31之间的整数，做为date对象的天数
            hours       - 0(午夜24点)-23之间的整数，做为date对象的小时数
            minutes     - 0-59之间的整数，做为date对象的分钟数
            seconds     - 0-59之间的整数，做为date对象的秒数
            microseconds - 0-999之间的整数，做为date对象的毫秒数
            ==================================================*/
            var t1 = Date.UTC(2017, 
                              5, 
                              19, 
                              0, 
                              0, 
                              0); //北京时间
            var t2 = Date.UTC(todayYear,todayMonth,todayDate,todayHour,todayMinute,todaySecond);
            var diff = t2-t1;
            var diffYears = Math.floor(diff/years);
            var diffDays = Math.floor((diff/days)-diffYears*365);
            var diffHours = Math.floor((diff-(diffYears*365+diffDays)*days)/hours);
            var diffMinutes = Math.floor((diff-(diffYears*365+diffDays)*days-diffHours*hours)/minutes);
            var diffSeconds = Math.floor((diff-(diffYears*365+diffDays)*days-diffHours*hours-diffMinutes*minutes)/seconds);
            document.getElementById("sitetime").innerHTML="已在这里 "+diffYears+" 年 "+diffDays+" 天 "+diffHours+" 小时 "+diffMinutes+" 分钟 "+diffSeconds+" 秒";
        }
        siteTime();
    </script>



    </div>
  </footer>

  
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/next-theme-pjax/0.6.0/pjax.min.js" integrity="sha256-vxLn1tSKWD4dqbMRyv940UYw4sXgMtYcK6reefzZrao=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/fancyapps-ui/5.0.28/fancybox/fancybox.umd.js" integrity="sha256-ytMJGN3toR+a84u7g7NuHm91VIR06Q41kMWDr2pq7Zo=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/lozad.js/1.16.0/lozad.min.js" integrity="sha256-mOFREFhqmHeQbXpK2lp4nA3qooVgACfh88fpJftLBbc=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  <script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.1/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>




  <script src="/js/third-party/fancybox.js"></script>

  <script src="/js/third-party/pace.js"></script>


  




  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.2/es5/tex-mml-chtml.js","integrity":"sha256-MASABpB4tYktI2Oitl4t+78w/lyA+D7b/s9GEP0JOGI="}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


 
        <div id="click-show-text"
            data-mobile = false
            data-text = 富强,民主,文明,和谐,自由,平等,公正,法制,爱国,敬业,诚信,友善
            data-fontsize = 15px
            data-random= false>
        </div>
       

      
        <script async src=https://cdn.jsdelivr.net/npm/hexo-next-mouse-effect@latest/click/showText.js></script>
      

      
    




    <script async src="/js/fancybox_param.js"></script>





<!-- APlayer本体 -->



</body>
</html>
